package com.dy.队列.求解素数环;
//将1到n排列成环形，相邻之和为素数

import com.dy.排序.内排序.SqlList;
import com.dy.线性表.顺序表.SqList;
import com.dy.队列.链队列.LinkQueue;

/**
 * 1、顺序表存放素数环的数据元素 L
 * 2、链队列存放还没加入到素数的自然数 Q
 * 3、将1加入到顺序表L，2到n加入队列Q
 * 4、队首和素数环最后一个相加，若是素数，加入，否则再次入队
 * 若为对尾元素，判断和环的第一个和是不是素数，是，求解结束
 * <p>
 * 只有奇数才可能是素数，而奇数=偶数+奇数，所以素数环一定是奇数偶数相间分布，
 * 所以n一定是偶数，如果是奇数那一定存在两奇数相邻情况。
 */

public class Solution {
    public boolean isPrime(int num) {
        if (num == 1) return false;
        double n = Math.sqrt(num);
        for (int i = 2; i <= (int) n; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public SqList makePrimeRing(int n) throws Exception {
        if (!(n % 2 == 0)) throw new Exception("素数环不存在");
        SqList L = new SqList(n);
        L.insert(0, 1);
        LinkQueue Q = new LinkQueue();
        for (int i = 2; i <= n; i++) {
            Q.offer(i);
        }
        return inserRing(L,Q,2,n);

    }
    public SqList inserRing(SqList l,LinkQueue q,int m,int n) throws Exception{
        int count=0;//记录遍历队列中元素的个数
        while(!q.isEmpty()&&count<=n-m){
            int a =(Integer)q.poll();
            int b = (Integer)l.get(l.length()-1);
            if(m==n){
                if(isPrime(a+b)&&isPrime(a+1)){
                    l.insert(l.length(),a);
                    return l;
                }
                else q.offer(a);
            }
            else if(isPrime(a+b)){
                l.insert(l.length(),a);
                if(inserRing(l,q,m+1,n)!=null){
                    return l;
                }
                l.remove(l.length());
                q.offer(a);
            }
            else q.offer(a);
            ++count;
        }
        return null;
    }

    public static void main(String[] args) throws Exception {
        Solution solution = new Solution();
        SqList l = solution.makePrimeRing(6);
         l.display();
    }
}
